|
In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs. Skew-symmetric graphs were first introduced under the name of ''antisymmetrical digraphs'' by , later as the double covering graphs of polar graphs by , and still later as the double covering graphs of bidirected graphs by . They arise in modeling the search for alternating paths and alternating cycles in algorithms for finding matchings in graphs, in testing whether a still life pattern in Conway's Game of Life may be partitioned into simpler components, in graph drawing, and in the implication graphs used to efficiently solve the 2-satisfiability problem. ==Definition== As defined, e.g., by , a skew-symmetric graph ''G'' is a directed graph, together with a function σ mapping vertices of ''G'' to other vertices of ''G'', satisfying the following properties: # For every vertex ''v'', σ(''v'') ≠ ''v'', # For every vertex ''v'', σ(σ(''v'')) = ''v'', # For every edge (''u'',''v''), (σ(''v''),σ(''u'')) must also be an edge. One may use the third property to extend σ to an orientation-reversing function on the edges of ''G''. The transpose graph of ''G'' is the graph formed by reversing every edge of ''G'', and σ defines a graph isomorphism from ''G'' to its transpose. However, in a skew-symmetric graph, it is additionally required that the isomorphism pair each vertex with a different vertex, rather than allowing a vertex to be mapped to itself by the isomorphism or to group more than two vertices in a cycle of isomorphism. A path or cycle in a skew-symmetric graph is said to be ''regular'' if, for each vertex ''v'' of the path or cycle, the corresponding vertex σ(''v'') is not part of the path or cycle. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Skew-symmetric graph」の詳細全文を読む スポンサード リンク
|